// 
use std::ptr;

pub struct QueueEntry {
    data: QueueValue,
    prev: Option<Box<QueueEntry>>,
    next: Option<Box<QueueEntry>>,
}

pub struct Queue {
    head: Option<Box<QueueEntry>>,
    tail: Option<Box<QueueEntry>>,
}

impl Queue {
    pub fn new() -> Option<Box<Queue>> {
        Some(Box::new(Queue {
            head: None,
            tail: None,
        }))
    }

    pub fn free(&mut self) {
        while !self.is_empty() {
            self.pop_head();
        }
    }

    pub fn push_head(&mut self, data: QueueValue) -> bool {
        let new_entry = Box::new(QueueEntry {
            data,
            prev: None,
            next: self.head.take(),
        });

        if let Some(entry) = self.head.replace(new_entry) {
            entry.prev = Some(new_entry);
        } else {
            self.tail = Some(new_entry);
        }

        true
    }

    pub fn pop_head(&mut self) -> QueueValue {
        if self.is_empty() {
            QUEUE_NULL
        } else {
            let entry = self.head.take().unwrap();
            let result = entry.data;

            if let Some(next_entry) = entry.next {
                self.head = Some(next_entry);
                self.head.as_mut().unwrap().prev = None;
            } else {
                self.tail = None;
            }

            result
        }
    }

    pub fn peek_head(&self) -> QueueValue {
        if self.is_empty() {
            QUEUE_NULL
        } else {
            self.head.as_ref().unwrap().data
        }
    }

    pub fn push_tail(&mut self, data: QueueValue) -> bool {
        let new_entry = Box::new(QueueEntry {
            data,
            prev: self.tail.take(),
            next: None,
        });

        if let Some(entry) = self.tail.replace(new_entry) {
            entry.next = Some(new_entry);
        } else {
            self.head = Some(new_entry);
        }

        true
    }

    pub fn pop_tail(&mut self) -> QueueValue {
        if self.is_empty() {
            QUEUE_NULL
        } else {
            let entry = self.tail.take().unwrap();
            let result = entry.data;

            if let Some(prev_entry) = entry.prev {
                self.tail = Some(prev_entry);
                self.tail.as_mut().unwrap().next = None;
            } else {
                self.head = None;
            }

            result
        }
    }

    pub fn peek_tail(&self) -> QueueValue {
        if self.is_empty() {
            QUEUE_NULL
        } else {
            self.tail.as_ref().unwrap().data
        }
    }

    pub fn is_empty(&self) -> bool {
        self.head.is_none()
    }
}
//  